package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.*;

/**
 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked
 * 通过
 *
 * @author yulongTian
 * @create 2024-06-26 22:11
 */
public class Test49 {
    public static void main(String[] args) {

    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    //递归实现
    private TreeNode ans = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return ans;
    }

    /**
     * 递归实现
     */
    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }

        boolean left = dfs(root.left, p, q);
        boolean right = dfs(root.right, p, q);
        if (left && right || (root == p || root == q) && (left || right)) {
            ans = root;
        }
        return left || right || (root == p) || root == q;
    }


//    // 也可以只存储数字
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        Map<TreeNode, TreeNode> map = new HashMap<>();
//        dfs(root, root, map);
////        map.put(new TreeNode(Integer.MIN_VALUE), new TreeNode(0));
////        for (TreeNode treeNode : map.keySet()) {
////            System.out.println(treeNode.val + "-" + map.get(treeNode).val);
////        }
//
//        Set<TreeNode> set = new HashSet<>();
//        TreeNode pp = p;
//        set.add(pp);
//        while (true) {
//            TreeNode ppp = map.get(pp);
//            set.add(ppp);
//            if (ppp == root) {
//                break;
//            }
//            pp = ppp;
//        }
////        for (Object o : set.toArray()) {
////            TreeNode t=(TreeNode)o;
////            System.out.println(t.val);
////        }
//        pp = q;
//        if (set.contains(pp)) {
//            return pp;
//        }
//        while (true) {
//            TreeNode ppp = map.get(pp);
//            if (set.contains(ppp)) {
//                break;
//            }
//            pp = ppp;
//        }
//
//        return map.get(pp);
//    }
//
//
//    private void dfs(TreeNode root, TreeNode parent, Map<TreeNode, TreeNode> map) {
//        if (root == null) {
//            return;
//        }
//        map.put(root, parent);
//        dfs(root.left, root, map);
//        dfs(root.right, root, map);
//    }


}
